#coding:gb2312

import heapq
class Graph(object):
	"""Reimplementation of Graph class according to PEP8--the coding style
	guide.
	"""
	def __init__(self):
		self.prev={}
		self.next={}

	def __str__(self):
		return "<graph object:"+str(self.next)+">"

	def __len__(self):
		return len(self.next)

	#methods that change internal state
	def add_node(self,node):
		assert node not in self.prev and node not in self.next
		self.prev[node]={}
		self.next[node]={}

	def add_nodes(self,nodes):
		for node in nodes:
			self.add_node(node)

	def add_arrow(self,arrow,dump_check=False):
		u,v=arrow
		assert u!=v #Loops are not allowed
		
		if u not in self.next:
			self.add_node(u)
		if v not in self.next:
			self.add_node(v)

		#check for dumplicated add
		if dump_check:
			assert not self.next[u].has_key(v)
			
		self.prev[v][u]=None
		self.next[u][v]=None

	def add_arrows(self,arrows,dump_check=False):
		for arrow in arrows:
			u,v=arrow
			self.add_arrow(u,v,dump_check)

	def add_edge(self,edge,dump_check=False):
		u,v=edge
		self.add_arrow((u,v),dump_check)
		self.add_arrow((v,u),dump_check)

	def add_edges(self,edges,dump_check=False):
		for edge in edges:
			self.add_edge(edge,dump_check)

	def del_node(self,node):
		assert node in self.next

		#remove arrow to this node
		for u in self.prev[node]:
			del self.next[u][node]
		
		#remove arrow from this node
		for u in self.next[node]:
			del self.prev[u][node]
		
		#remove node
		del self.prev[node]
		del self.next[node]

	def del_arrow(self,arrow,check=False):
		u,v=arrow
		if self.next[u].has_key(v):
			del self.prev[v][u]
			del self.next[u][v]
		elif check:
			assert self.next[u].has_key(v)

	def del_edge(self,edge,check=False):
		u,v=edge
		self.del_arrow((u,v),check)
		self.del_arrow((v,u),check)

	#viewing methods
	def nodes(self):
		return self.next.iterkeys()

	def links(self):
		for u in self.next:
			for v in self.next[u]:
				yield (u,v)

	def prev_nodes(self,node):
		return self.prev[node].iterkeys()

	def next_nodes(self,node):
		return self.next[node].iterkeys()

	def has_node(self,node):
		return self.next.has_key(node)

	def has_arrow(self,arrow):
		u,v=arrow
		try:
			self.next[u][v]
		except:
			return False
		
		return True

	def has_edge(self,edge):
		u,v=edge
		return self.has_arrow((u,v)) and self.has_arrow((v,u))

def single_source_shortest_paths(graph,o,wmap):
	assert o in graph.nodes()

	dists={}
	paths={o:[o]}
	seen={o:0}
	fringe=[]
	heapq.heappush(fringe,(0,o))

	while fringe:
		d,v=heapq.heappop(fringe)
		if v in dists:
			continue
		dists[v]=seen[v]
		for w in graph.next_nodes(v):
			vw_dist=dists[v]+wmap[(v,w)]
			if w in dists:
				assert vw_dist>=dists[w]
			elif w not in seen or vw_dist<seen[w]:
				seen[w]=vw_dist
				paths[w]=paths[v]+[w]
				heapq.heappush(fringe,(vw_dist,w))
	
	return paths,dists

def shortest_paths(g,os,ds,ttmap):
	paths={}
	dists={}

	for o in os:
		_paths,_dists=single_source_shortest_paths(g,o,ttmap)
		for d in ds:
			if d!=o:
				paths[(o,d)]=_paths[d]
				dists[(o,d)]=_dists[d]
	
	#print paths.keys()
	return paths,dists

if __name__=="__main__":
	g=Graph()
	print g
	print
	g.add_nodes([1,2,3,4,5])
	print g
	print
	g.add_edges([(1,2),(2,3),(3,4),(4,5),(5,1)])
	print g

	class _ConstWeight:
		def __getitem__(self,key):
			return 1
	wmap=_ConstWeight()

	paths,dists=single_source_shortest_paths(g,1,wmap)
	print paths,dists
	paths,dists=shortest_paths(g,[1,2,3,4,5],[1,2,3,4,5],wmap)
	print paths

	

